This paper introduces the notion of a universal plan, which when executed, is guaranteed to solve all planning problems in a category, regardless of the obstacles, initial state, and goal set. Such plans are specified as a deterministic sequence of actions that are blindly applied without any sensor feedback. Thus, they can be considered as pure exploration in a reinforcement learning context, and we show that with basic memory requirements, they even yield asymptotically optimal plans. Building upon results in number theory and theory of automata, we provide universal plans both for discrete and continuous (motion) planning and prove their (semi)completeness. The concepts are applied and illustrated through simulation studies, and several directions for future research are sketched.

To present a sharp criticism of the approach known as universal planning, I begin by giving a precise definition of it. The key idea in this work is that an agent is working to achieve some goal and that to determine what to do next in the pursuit of this goal, the agent finds its current situation in a large table that prescribes the correct action to take. Of course, the action suggested by the table might simply be, "Think about your current situation and decide what to do next." This method is, in many ways, representative of the conventional approach to planning; however, what distinguishes universal plans from conventional plans is that the action suggested by a universal plan is always a primitive one that the agent can execute immediately (Agre and Chapman 1987; Drummond 1988; Kaelbling 1988; Nilsson 1989; Rosenschein and Kaelbling 1986; Schoppers 1987). Several authors have recently suggested that a possible approach to planning in uncertain domains is to analyze all possible situations beforehand and then store information about what to do in each.

Until quite recently, it was taken for granted in AIand cognitive science more broadlythat activity resulted from the creation and execution of plans. In 1985, several researchers, including myself, independently realized that plans and planning are not necessary-or necessarily useful-in activity. Since this time, a number of alternatives have been proposed. This analysis is equally applicable to any other computational problem. Thus, you could conclude that vision is impossible because it requires exponential computation in the number of pixels or that, on the average, business data processing takes exponential work in the number of records.

Ginsberg raises two issues for our consideration: (1) universal plans that do not allow cognitive actions (run-time problem solving) might need an exponential amount of space or circuitry for their realization and (2) universal plans that do allow cognitive actions will spend so much time on these actions that the universal plan itself can be largely superfluous. In sum, depending on whether planning is allowed to supplement a universal plan, the universal plan itself is likely to be either infeasible or superfluous, respectively. Let me clear up some areas of potential confusion. Although universal plans had the title role in Ginsberg's article, he is actually discussing a small group of related endeavors that are more commonly known as reactive Universal plans address the tension between reasoned behavior and timely response by caching reactions for classes of possible situations. This technique reduces the average time required to select a response at the expense of the space required to store the cache--the classic timespace tradeoff.

Recently model checking representation and search techniques were shown to be efficiently applicable to planning, in particular to non-deterministic planning. Such planning approaches use Ordered Binary Decision Diagrams (OBDDs) to encode a planning domain as a non-deterministic finite automaton and then apply fast algorithms from model checking to search for a solution. OBDDs can effectively scale and can provide universal plans for complex planning domains. We are particularly interested in addressing the complexities arising in non-deterministic, multi-agent domains. In this article, we present UMOP, a new universal OBDD-based planning framework for non-deterministic, multi-agent domains. We introduce a new planning domain description language, NADL, to specify non-deterministic, multi-agent domains. The language contributes the explicit definition of controllable agents and uncontrollable environment agents. We describe the syntax and semantics of NADL and show how to build an efficient OBDD-based representation of an NADL description. The UMOP planning system uses NADL and different OBDD-based universal planning algorithms. It includes the previously developed strong and strong cyclic planning algorithms. In addition, we introduce our new optimistic planning algorithm that relaxes optimality guarantees and generates plausible universal plans in some domains where no strong nor strong cyclic solution exists. We present empirical results applying UMOP to domains ranging from deterministic and single-agent with no environment actions to non-deterministic and multi-agent with complex environment actions. UMOP is shown to be a rich and efficient planning system.

Since this article is a counting argument, the conclusion time, a number of alternatives have been proposed. Presumably, in realistic cases, the Universally Bad Idea," analyzes one such number of sensors is large enough that a universal alternative, Marcel Schoppers's universal plan could not fit in your head. He also extends this analysis to a There are two reasons not to be concerned number of other systems, including Pengi about this apparent problem. They involve (A gre and Chapman 1987), which was structure and state, designed by Phil Agre and myself. Ginsberg's criticisms of universal plans rest Using universal plans, he says, is infeasible because their size is exponential in the number of possible domain states. Representing such a plan is infeasible in even quite small realistic domains. I'm sympathetic to such arguments, having made similar ones to the effect that classical planning is infeasible (Agre and Chapman 1988; Chapman 1987b). I don't understand the details of Schoppers's ideas, so I'm not sure whether this critique of universal plans per se is correct. However, I show that these arguments do not extend to Pengi. Ginsberg calls Pengi an approximate universal plan, by which he means it is like a universal plan except that it does not correctly specify what to do in every situation. However, Pengi's operation involves no plans, universal or approximate, and Pengi and universal plans, although they share some motivations, have little to do with each other as technical proposals. Ginsberg suggests number of its inputs. Pengi-like system, computation in the number of pixels or that, Blockhead, which efficiently solves the fruitcake on the average, business data processing takes problem; the way it solves it elucidates exponential work in the number of records. They have a lot The fruitcake problem is to stack a set of of structure to them, and this structure can be labeled blocks so that they spell the word exploited to exponentially reduce the computation's fruitcake. What is apparently difficult about size. I show impossible under the rules of the domain, Blockhead solving a problem involving 45 and the remainder can be categorized relatively blocks in which there are 45! 1056 configurations, cheaply to permit abstraction and There is every in every configuration, so it is not by reason to think that this same structure is approximation that it succeeds. Indeed, Ginsberg makes this and a central system. The [planning couldn't work if] there were no visual system is a small subset of Pengi's rhyme or reason to things."

Several authors have recently suggested that a possible approach to planning in uncertain domains is to analyze all possible situations beforehand and then store information about what to do in each. The result is that a system can simply use its sensors to examine its domain and then decide what to do by finding its current situation in some sort of a table. The purpose of this article is to argue that even if the compile-time costs of the analysis are ignored, the size of the table must, in general, grow exponentially with the complexity of the domain. This growth makes it unlikely that this approach to planning will be able to deal with problems of an interesting size; one really needs the ability to do some amount of inference at run time. In other words, an effective approach to acting in uncertain domains cannot be to look and then leap; it must always be to look, to think, and only then to leap.

Universal plans address the tension between reasoned behavior and timely response by caching reactions for classes of possible situations. This technique reduces the average time required to select a response at the expense of the space required to store the cache-the classic time-space trade-off. In his article, Matthew Ginsberg argues from the time extreme and against the space extreme. Although I find both extremes undesirable, I defend an increase in space consumption.